home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 2010 April / PCWorld0410.iso / pluginy Firefox / 2410 / 2410.xpi / chrome / content / foxmarks-core.js < prev    next >
Text File  |  2010-01-28  |  30KB  |  881 lines
  1.  /*
  2.  Copyright 2007 Foxmarks Inc.
  3.  
  4.  foxmarks-core.js: implements core sync & merge algorithms. 
  5.  
  6.  */
  7.  
  8. function EnumerateDeletedNodes(cs, baseline, current) {
  9.     // Given a delete command, determine which of its desecendant nodes
  10.     // were actually deleted, and attach that list of nids.
  11.     // Some children may have been moved prior to the delete, so they
  12.     // would survive in the curernt nodeset. Those survivors are not
  13.     // included in the attached list.
  14.  
  15.     
  16.     var deleted = null;
  17.  
  18.     function EnumerateInternal(nid) {
  19.         if (!current.Node(nid, false, true)) {
  20.             deleted.push(nid);
  21.         }
  22.         var node = baseline.Node(nid);
  23.         if (node.children) {
  24.             node.children.forEach(function(nid) { EnumerateInternal(nid) } );
  25.         }
  26.     }
  27.  
  28.     cs.set.forEach(function(command) {
  29.         if (command.action == 'delete') {
  30.             command.deleted = [];
  31.             deleted = command.deleted;
  32.             EnumerateInternal(command.nid);
  33.         }
  34.     } );
  35. }
  36.  
  37. function CleanDeletedNodes(cs) {
  38.     cs.set.forEach(function(cmd) { 
  39.         if (cmd.action == 'delete') {
  40.             delete cmd.deleted;
  41.         }
  42.         delete cmd.fixed;
  43.     } );
  44. }
  45.  
  46.  
  47. function CombinePrePost(cs) {
  48.     cs.set = cs.pre.concat(cs.set).concat(cs.post);
  49.     delete cs.pre;
  50.     delete cs.post;
  51. }
  52.  
  53. function OpenConflictDialog(url, input) {
  54.     // find a browser window to use as a parent for openDialog
  55.     var wm = Cc['@mozilla.org/appshell/window-mediator;1'].getService();
  56.     var wmi = wm.QueryInterface(Ci.nsIWindowMediator);
  57.     var top = wmi.getMostRecentWindow("foxmarks:progress");
  58.  
  59.     // If we can't find one of our own windows, try any window.
  60.     if (!top) {
  61.         top = wmi.getMostRecentWindow(null);
  62.         if (!top) {
  63.             // We couldn't find a window, so pretend user canceled.
  64.             return null;
  65.         }
  66.     }
  67.  
  68.     var output = {};
  69.     top.openDialog(url, "_blank", "chrome,dialog,modal,centerscreen", 
  70.         output, input);
  71.     return output.selection;
  72. }
  73.  
  74.  
  75.  
  76. var DETECTORS = {
  77.  
  78.     // Format for naming of these detectors is localaction_serveraction.
  79.  
  80.     insert_insert: function(local, server, localNS, serverNS) {
  81.         if (local.nid == server.nid) {  // items created with same nid. Scary!
  82.             var conflict = [];
  83.  
  84.             forEach(local.args, function(value, attr) {
  85.                 if (server.args[attr] && !DETECTORS.HARMLESS_ATTRS[attr] &&
  86.                         value != server.args[attr]) {
  87.                     conflict.push(attr + ":" + value);
  88.                 }
  89.             } );
  90.  
  91.             forEach(server.args, function(value, attr) {
  92.                 if (local.args[attr] && !DETECTORS.HARMLESS_ATTRS[attr] &&
  93.                         value != local.args[attr]) {
  94.                     conflict.push(attr + ":" + value);
  95.                 }
  96.             } );
  97.  
  98.             if (conflict.length) {
  99.                 var lnode = localNS.Node(local.nid);
  100.                 var snode = serverNS.Node(server.nid);
  101.                 var rv = localNS.handleNidConflict(lnode, snode, conflict);
  102.  
  103.                 showedUI = true;
  104.  
  105.                 if (rv == "local") {
  106.                     return ["overwrite", "local"];
  107.                 } else if (rv == "server") {
  108.                     return ["overwrite", "server"];
  109.                 } else if (rv == "same") {
  110.                     return ["drop", "both"];
  111.                 } else {
  112.                     throw 2;
  113.                 }
  114.             } else {
  115.                 return ["drop", "both"];
  116.             }
  117.         }
  118.         if (local.args.pnid == server.args.pnid &&
  119.                 local.args.bnid == server.args.bnid) {
  120.             return ["transit", "server"];
  121.         }
  122.         return null;
  123.     },
  124.  
  125.     insert_move: function(local, server) {
  126.         if (local.args.pnid != server.args.pnid &&
  127.             local.args.bnid == server.nid) {
  128.             return ["nextsib", "left"];
  129.         }
  130.         if (local.nid != server.nid &&
  131.                 local.args.pnid == server.args.pnid &&
  132.                 local.args.bnid == server.args.bnid) {
  133.                 return ["transit", "server"];
  134.         }
  135.         return null;
  136.     },
  137.  
  138.     insert_reorder: function(local, server, lns, sns) {
  139.         if (local.args.pnid == sns.Node(server.nid).pnid &&
  140.                 local.args.bnid == server.args.bnid && !server.fixed) {
  141.             return ["transit", "server"]; 
  142.         }
  143.         if (local.args.pnid == sns.Node(server.nid).pnid &&
  144.                 local.args.bnid == server.nid) {
  145.             return ["nextsib", "left"];
  146.         }
  147.         return null;
  148.     },
  149.  
  150.     insert_update: function(local, server) {
  151.         return null;
  152.     },
  153.  
  154.     delete_insert: function(local, server) {
  155.         if (local.deleted.indexOf(server.args.bnid) >= 0) {
  156.             return ["nextsib", "right"];
  157.         }
  158.         if (local.deleted.indexOf(server.args.pnid) >= 0) {
  159.             return ["delinsert", "left"];
  160.         }
  161.         return null;
  162.     },
  163.             
  164.     delete_delete: function(local, server) {
  165.         if (local.nid == server.nid) {
  166.             return ["drop", "both"];
  167.         }
  168.         if (local.deleted.indexOf(server.nid) >= 0) {
  169.             return ["drop", "right"];
  170.         }
  171.  
  172.         if (server.deleted.indexOf(local.nid) >= 0) {
  173.             return ["drop", "left"];
  174.         }
  175.  
  176.         return null;
  177.     },
  178.  
  179.     delete_move: function(local, server) {
  180.         if (local.deleted.indexOf(server.args.bnid) >= 0) {
  181.             return ["nextsib", "right"];
  182.         }
  183.         if (local.deleted.indexOf(server.nid) >= 0) {
  184.             return ["delmoveout", "left"];
  185.         }
  186.         if (local.deleted.indexOf(server.args.pnid) >= 0) {
  187.             return ["delmovein", "left"];
  188.         }
  189.         return null;
  190.     },
  191.  
  192.     delete_reorder: function(local, server) {
  193.         if (local.deleted.indexOf(server.nid) >= 0) {
  194.             return ["drop", "right"];
  195.         }
  196.         if (local.nid == server.args.bnid) {
  197.             return ["nextsib", "right"];
  198.         }
  199.         return null;
  200.     },
  201.  
  202.     delete_update: function(local, server) {
  203.         if (local.deleted.indexOf(server.nid) >= 0) {
  204.             // A modified node was deleted. If the modifications
  205.             // were significant, we've got a real conflict. Otherwise,
  206.             // drop the modification and proceed with the delete.
  207.             for (var a in server.args) {
  208.                 if (server.args.hasOwnProperty(a) &&
  209.                         !DETECTORS.HARMLESS_ATTRS[a]) {
  210.                     return ["delupdate", "left"];
  211.                 }
  212.             }
  213.             // The update was insignificant; drop it.
  214.             return ["drop", "right"];
  215.         }
  216.         return null;
  217.     },
  218.  
  219.     move_move: function(local, server, localNS, serverNS) {
  220.         if (local.args.pnid == server.args.pnid) {
  221.             if (local.nid == server.nid) {
  222.                 if (local.args.bnid == server.args.bnid) {
  223.                     return ["drop", "both"];
  224.                 } else {
  225.                     return ["drop", "server"];
  226.                 }
  227.             } else {
  228.                 if (local.args.bnid == server.args.bnid) {
  229.                     return ["transit", "server"];
  230.                 }
  231.             }
  232.         } else {
  233.             if (local.nid == server.nid) {
  234.                 var input = { item: localNS.Node(local.nid),
  235.                     local: localNS.Node(local.args.pnid),
  236.                     server: serverNS.Node(server.args.pnid) };
  237.                 var rv = OpenConflictDialog(
  238.                     "chrome://foxmarks/content/foxmarks-parentconflict.xul",
  239.                     input);
  240.                 showedUI = true;
  241.  
  242.                 if (rv == "local") {
  243.                     return ["drop", "server"];
  244.                 } else if (rv == "server") {
  245.                     return ["drop", "local"];
  246.                 } else {
  247.                     throw 2;
  248.                 }
  249.             } else {
  250.                 if (local.nid == server.args.bnid) {
  251.                     return ["nextsib", "right"];
  252.                 } else if (local.args.bnid == server.nid) {
  253.                     return ["nextsib", "left"];
  254.                 }
  255.             }
  256.         }
  257.  
  258.         return null;
  259.     },
  260.  
  261.     move_reorder: function(local, server, lns, sns) {
  262.         if (local.nid == server.nid) {
  263.             return ["drop", "right"];
  264.         }
  265.         if (local.nid == server.args.bnid &&
  266.                 local.args.pnid != sns.Node(server.nid).pnid &&
  267.                 !server.fixed) {
  268.             return ["nextsib", "right"];
  269.         }
  270.         if (local.args.pnid == sns.Node(server.nid).pnid &&
  271.                 local.args.bnid == server.args.bnid &&
  272.                 !server.fixed) {
  273.             return ["transit", "server"];
  274.         }
  275.         return null;
  276.     },
  277.  
  278.     move_update: function() {
  279.         return null;
  280.     },
  281.  
  282.     reorder_reorder: function(local, server, lns, sns) {
  283.         if (lns.Node(local.nid).pnid != sns.Node(server.nid).pnid) {
  284.             return null;
  285.         }
  286.         if (local.nid == server.nid) {
  287.             if (local.args.bnid == server.args.bnid) {
  288.                 if (!local.fixed) {
  289.                     return ["drop", "both"];
  290.                 } else {
  291.                     return null;
  292.                 }
  293.             } else {
  294.                 // XXX: Must retarget in this case
  295.                 return ["drop", "server"];
  296.             }
  297.         } else { // local.nid != server.nid
  298.             if (local.nid == server.args.bnid && !server.fixed) {
  299.                 return ["commutereorder", "left"];
  300.             } else if (local.args.bnid == server.nid && !local.fixed) {
  301.                 return ["commutereorder", "right"];
  302.             } else {
  303.                 return null;
  304.             }
  305.         }
  306.     },
  307.  
  308.     reorder_update: function() {
  309.         return null;
  310.     },
  311.  
  312.     HARMLESS_ATTRS: { created: true, visited: true, modified: true, private: true, 
  313.         icon: true },
  314.  
  315.     update_update: function(local, server, localNS, serverNS) {
  316.         if (local.nid != server.nid)
  317.             return;
  318.  
  319.         var conflicts = [];
  320.  
  321.         forEach(local.args, function(value, attr) {
  322.             if (server.args[attr] && !DETECTORS.HARMLESS_ATTRS[attr] &&
  323.                     value != server.args[attr]) {
  324.                 conflicts.push(attr);
  325.             }
  326.         } );
  327.  
  328.         // Special case: tag-only conflict
  329.         if (conflicts.length == 1 && conflicts[0] == 'tags') {
  330.             return ["drop", "server"];
  331.         }
  332.  
  333.         // Special case: conflict on (hidden attributes of) ROOT
  334.         if (local.nid == NODE_ROOT) {
  335.             return ["drop", "server"];
  336.         }
  337.  
  338.         if (conflicts.length) {
  339.             var lnode = localNS.Node(local.nid);
  340.             var snode = serverNS.Node(server.nid);
  341.             var rv = localNS.handleNidConflict(lnode, snode, conflicts);
  342.  
  343.             showedUI = true;
  344.             if (rv == "local") {
  345.                 return ["drop", "server"];
  346.             } else if (rv == "server") {
  347.                 return ["drop", "local"];
  348.             } else if (rv == "same") {
  349.                 return ["drop", "both"];
  350.             } else {
  351.                 throw 2;
  352.             }
  353.         } 
  354.         return null;
  355.     }
  356. }
  357.  
  358.  
  359.  
  360. // Given a baseline nodeset, a local nodeset, and a server nodeset,
  361. // generate two commandsets, one to be applied to the local nodeset,
  362. // another to be applied to the server nodeset. Applying each commandset
  363. // to the respective nodeset will result in the two nodsets becoming
  364. // synchronized.
  365. //
  366. // Note that the routine operates asynchronously; the client-provided
  367. // callback will be called with two parameters: localCS (the commandset
  368. // to be applied to the server, and serverCS (the commandset to be applied
  369. // to the local nodeset).
  370.  
  371. function Synchronize(baseline, localCS, serverCS, local, server, callback) {
  372.  
  373.     EnumerateDeletedNodes(localCS, baseline, local);
  374.     EnumerateDeletedNodes(serverCS, baseline, server);
  375.  
  376.     localCS.pre = [];
  377.     localCS.post = [];
  378.     serverCS.pre = [];
  379.     serverCS.post = [];
  380.  
  381.     // Iterate over each local commmand, comparing it with each
  382.     // server command. Detect and resolve conflicts.
  383.  
  384.     var iterations = 0;
  385.     var conflicts = {};
  386.     var showedUI = false;
  387.  
  388.     for (var l = 0; l < localCS.set.length; ++l) {
  389.         var lc = localCS.set[l];
  390.         var result = null;
  391.         var breakOut = false;
  392.  
  393.         for (var s = 0; s < serverCS.set.length; ++s) {
  394.  
  395.             sc = serverCS.set[s];
  396.  
  397.             var method = DETECTORS[lc.action + "_" + sc.action];
  398.             if (method) {
  399.                 try {
  400.                     result = method(lc, sc, local, server, false);
  401.                 } catch (e) {
  402.                     Xmarks.LogWrite("Synchronize: failed processing " +
  403.                         lc.toSource() + ", " + sc.toSource());
  404.                     Xmarks.LogWrite("Error is " + e.toSource());
  405.                     throw e;
  406.                 }
  407.                 if (!result)
  408.                     continue;
  409.                 if (result[1] == 'left') result[1] = 'local';
  410.                 else if (result[1] == 'right') result[1] = 'server';
  411.             } else {
  412.                 method = DETECTORS[sc.action + "_" + lc.action];
  413.                 if (!method) {
  414.                     throw Error("Couldn't find conflict detector for " +
  415.                             lc.action + " : " + sc.action);
  416.                 }
  417.                 try {
  418.                     result = method(sc, lc, server, local, true);
  419.                 } catch (e) {
  420.                     Xmarks.LogWrite("Synchronize: failed processing (reversed) " +
  421.                         sc.toSource() + ", " + lc.toSource());
  422.                     Xmarks.LogWrite("Error is " + e.toSource());
  423.                     throw e;
  424.                 }
  425.                 if (!result)
  426.                     continue;
  427.                 if (result[1] == 'left') result[1] = 'server';
  428.                 else if (result[1] == 'right') result[1] = 'local';
  429.             }
  430.            
  431.             conflicts[result[0]] = (conflicts[result[0]] || 0) + 1;
  432.  
  433.             Xmarks.LogWrite(">>> Sync: Executing " + result[0] + "(" + result[1] + 
  434.                     ") on " + lc.toSource() + " vs. " + sc.toSource());
  435.  
  436.             switch (result[0]) {
  437.             case 'drop': do_drop(result[1]); break;
  438.             case 'overwrite': do_overwrite(result[1]); break;
  439.             case 'transit': do_transit(result[1]); break;
  440.             case 'nextsib': do_nextsib(result[1]); break;
  441.             case 'delinsert': do_delinsert(result[1]); break;
  442.             case 'delmovein': do_delmovein(result[1]); break;
  443.             case 'delmoveout': do_delmoveout(result[1]); break;
  444.             case 'delupdate': do_delupdate(result[1]); break;
  445.             case 'commutereorder': do_commutereorder(result[1]); break;
  446.             default: throw Error("Unknown sync operator " + result[0]);
  447.             }
  448.  
  449.             if (breakOut) {
  450.                 iterations += 1;
  451.                 if (iterations >= 1000) {
  452.                     throw 1013;
  453.                 }
  454.                 break;
  455.             }
  456.         }
  457.     }
  458.  
  459.     // We have resolved all conflicts in commands
  460.     CleanDeletedNodes(localCS);
  461.     CleanDeletedNodes(serverCS);
  462.     CombinePrePost(localCS);
  463.     CombinePrePost(serverCS);
  464.  
  465.     callback(localCS, serverCS, conflicts, showedUI);
  466.     return;
  467.  
  468.     function do_overwrite(arg) {
  469.         switch (arg) {
  470.         case 'local': 
  471.             serverCS.drop(s); 
  472.             s = s - 1;
  473.             localCS.set[l].action = "update";
  474.             localCS.set[l].args.bnid = undefined;
  475.             localCS.set[l].args.pnid = undefined;
  476.             break;
  477.         case 'server': 
  478.             localCS.drop(l); 
  479.             l = l - 1;
  480.             serverCS.set[s].action = "update";
  481.             serverCS.set[s].args.bnid = undefined;
  482.             serverCS.set[s].args.pnid = undefined;
  483.             break;
  484.         default: 
  485.             throw Error("Unknown sync parameter " + result[1]);
  486.         }
  487.         return;
  488.     }
  489.     function do_drop(arg) {
  490.         switch (arg) {
  491.         case 'both': 
  492.             localCS.drop(l);
  493.             serverCS.drop(s);
  494.             l = l - 1;
  495.             breakOut = true;
  496.             // bust out of inner loop; decrement l and start there
  497.             break;
  498.         case 'local': 
  499.             localCS.drop(l); 
  500.             l = l - 1;
  501.             breakOut = true;
  502.             // bust out of inner loop; decrement l and start there
  503.             break;
  504.         case 'server': 
  505.             serverCS.drop(s); 
  506.             s = s - 1;
  507.             // decrement s and continue inner loop
  508.             break;
  509.         default: 
  510.             throw Error("Unknown sync parameter " + result[1]);
  511.         }
  512.         return;
  513.     }
  514.  
  515.     function do_transit(arg) {
  516.         switch (arg) {
  517.         case 'local': 
  518.             lc.args.bnid = sc.nid; 
  519.             l = l - 1;
  520.             breakOut = true;
  521.             // restart inner loop
  522.             break;
  523.         case 'server': 
  524.             sc.args.bnid = lc.nid; 
  525.             l = -1;
  526.             breakOut = true;
  527.             // restart outer loop
  528.             break;
  529.         default: 
  530.             throw Error("Uknown sync parameter " + result[1]);
  531.         }
  532.         return;
  533.     }
  534.  
  535.     function do_nextsib(arg) {
  536.         switch (result[1]) {
  537.         case 'local': 
  538.             lc.args.bnid = local.NextSibling(lc.args.bnid, baseline); 
  539.             l = l - 1;
  540.             breakOut = true;
  541.             // restart inner loop
  542.             break;
  543.         case 'server': 
  544.             sc.args.bnid = server.NextSibling(sc.args.bnid, baseline);
  545.             l = -1;
  546.             breakOut = true;
  547.             // restart outer loop
  548.             break;
  549.         default:
  550.             throw Error("Unknown sync parameter " + result[1]);
  551.         }
  552.         return;
  553.     }
  554.  
  555.     function do_delinsert(arg) {
  556.         // arg is local or server, determining which side
  557.         // originated the delete. The other side originated a
  558.         // conflicting insert. The desired end result is for the inserted
  559.         // node to be inserted into the nearest remaining ancestor of the
  560.         // original pnid. This is accomplished by modifying the existing
  561.         // insert command, changing its parent, and inserting a move command
  562.         // to the side that originated the delete which moves the already
  563.         // inserted node into the correct parent before performing the delete.
  564.         // Finally, we add reorders to the post-sequence so make sure that
  565.         // the inserted item ends up at the bottom of the folder.
  566.  
  567.         var del = null;
  568.         var ins = null;
  569.         var delCS = null;
  570.  
  571.         if (arg == "server") {
  572.             del = sc;
  573.             ins = lc;
  574.             delCS = serverCS;
  575.         } else {
  576.             del = lc;
  577.             ins = sc;
  578.             delCS = localCS;
  579.         }
  580.  
  581.         // What's the ultimate destination for the insert?
  582.         var pnid = NearestAncestor(ins.args.pnid, baseline, local, server);
  583.  
  584.         // Alter the insert command so that it winds up in a safe home.
  585.         ins.args.pnid = pnid;
  586.         ins.args.bnid = null;
  587.  
  588.         // Move the inserted node aside before the delete
  589.         delCS.pre.push(new Command("move", ins.nid, { pnid: pnid } ));
  590.  
  591.         // And now make sure it's add the end of the folder on both sides.
  592.         var cmd = new Command("reorder", ins.nid, { bnid: null } );
  593.         localCS.post.push(cmd);
  594.         serverCS.post.push(cmd);
  595.  
  596.         // We've modified both commandsets; restart processing from the top.
  597.         l = -1;
  598.         breakOut = true;
  599.         return;
  600.     }
  601.  
  602.     function do_delmovein(arg) {
  603.         // arg is local or server, determining which side
  604.         // originated the delete. The other side originated a
  605.         // conflicting move into the deleted subtree.
  606.         // The desired end result is for the moved
  607.         // node to be inserted into the nearest remaining ancestor of the
  608.         // original pnid. This is accomplished by modifying the existing
  609.         // move command, changing its parent, and inserting a move command
  610.         // to the side that originated the delete which moves the already
  611.         // inserted node into the correct parent before performing the delete.
  612.  
  613.         var del = null;
  614.         var ins = null;
  615.         var delCS = null;
  616.  
  617.         if (arg == "server") {
  618.             del = sc;
  619.             ins = lc;
  620.             delCS = serverCS;
  621.         } else {
  622.             del = lc;
  623.             ins = sc;
  624.             delCS = localCS;
  625.         }
  626.  
  627.         // What's the ultimate destination for the move?
  628.         var pnid = NearestAncestor(ins.args.pnid, baseline, local, server);
  629.  
  630.         // Alter the move command so that it winds up in a safe home.
  631.         ins.args.pnid = pnid;
  632.         ins.args.bnid = null;
  633.  
  634.         // Move the inserted node aside before the delete
  635.         delCS.pre.push(new Command("move", ins.nid, { pnid: pnid } ));
  636.  
  637.         // And now make sure it's add the end of the folder on both sides.
  638.         var cmd = new Command("reorder", ins.nid, { bnid: null } );
  639.         localCS.post.push(cmd);
  640.         serverCS.post.push(cmd);
  641.  
  642.         // We've modified both commandsets; restart processing from the top.
  643.         l = -1;
  644.         breakOut = true;
  645.         return;
  646.     }
  647.  
  648.     function do_delupdate(arg) {
  649.         // arg is local or server, determining which side
  650.         // originated the delete. The other side originated a
  651.         // conflicting update within the deleted subtree.
  652.         // The desired end result is for the updated node and its
  653.         // descendants to survive at the nearest remaining ancestor of the
  654.         // original destination. This is accomplished by resurrecting the
  655.         // modified node and its descendants and adding a move to the side
  656.         // from which the delete originated which moves the item to its new
  657.         // location.
  658.  
  659.         var update = null;
  660.         var updateCS = null;
  661.         var moveNS = null;
  662.         var del = null;
  663.         var delNS = null
  664.         var delIndex = 0;
  665.         var updateIndex = 0;
  666.  
  667.         if (arg == "server") {
  668.             update = lc;
  669.             updateCS = localCS;
  670.             updateNS = local;
  671.             del = sc;
  672.             delNS = server;
  673.             delCS = serverCS;
  674.             delIndex = s;
  675.             updateIndex = l;
  676.         } else {
  677.             update = sc;
  678.             updateCS = serverCS;
  679.             updateNS = server;
  680.             del = lc;
  681.             delNS = local;
  682.             delCS = localCS;
  683.             delIndex = l;
  684.             updateIndex = s;
  685.         }
  686.  
  687.         // Resurrect the deleted nodes
  688.         var pnid = ResurrectNodes(update.nid, baseline, updateNS, 
  689.             delNS, updateCS, updateIndex, del, delCS, delIndex, null);
  690.  
  691.         // On the delete side, add a move of the referenced node
  692.         // ... but only if it's a different parent.
  693.         if (pnid != updateNS.Node(update.nid).pnid) {
  694.             delCS.pre.push( new Command("move", update.nid, { pnid: pnid } ));
  695.         }
  696.  
  697.         // Push it to the end of its parent folder for safety
  698.         if(updateNS.OrderIsImportant()){
  699.             var cmd = new Command("reorder", update.nid, { bnid: null } );
  700.             localCS.post.push(cmd);
  701.             serverCS.post.push(cmd);
  702.         }
  703.  
  704.         // We've modified both commandsets; restart processing from the top.
  705.         l = -1;
  706.         breakOut = true;
  707.         return;
  708.     }
  709.  
  710.     function do_delmoveout(arg) {
  711.         // arg is local or server, determining which side
  712.         // originated the delete. The other side originated a
  713.         // conflicting move out of the deleted subtree.
  714.         // The desired end result is for the moved
  715.         // node to survive at the nearest remaining ancestor of the
  716.         // original destination. This is accomplished by replacing the existing
  717.         // move command with a (series of) insert(s) that resurrect the deleted
  718.         // nodes(s) in their correct position. We let delinsert deal with the
  719.         // case where the destination folder has also been deleted.
  720.  
  721.         var move = null;
  722.         var moveCS = null;
  723.         var moveIndex = null;
  724.         var moveNS = null;
  725.         var del = null;
  726.         var delNS = null
  727.         var delCS = null;
  728.         var delIndex = 0;
  729.  
  730.         if (arg == "server") {
  731.             move = lc;
  732.             moveCS = localCS;
  733.             moveIndex = l;
  734.             moveNS = local;
  735.             del = sc;
  736.             delNS = server;
  737.             delCS = serverCS;
  738.             delIndex = s;
  739.         } else {
  740.             move = sc;
  741.             moveCS = serverCS;
  742.             moveIndex = s;
  743.             moveNS = server;
  744.             del = lc;
  745.             delNS = local;
  746.             delCS = localCS;
  747.             delIndex = l;
  748.         }
  749.  
  750.         // Remove the move command
  751.         moveCS.set.splice(moveIndex, 1);
  752.  
  753.         // Resurrect the deleted nodes
  754.         ResurrectNodes(move.nid, baseline, moveNS, delNS, moveCS, moveIndex,
  755.             del, delCS, delIndex, move.args.bnid);
  756.  
  757.         // We've modified both commandsets; restart processing from the top.
  758.         l = -1;
  759.         breakOut = true;
  760.         return;
  761.     }
  762.  
  763.     function do_commutereorder(arg) {
  764.         // We've encountered R(x,y) vs. R(y,z).
  765.         // arg determines the side receiving the additional command R(x,y).
  766.         // The resolution is to add R(x,y) as a simulated command
  767.         // after R(y,z). We also mark the original R(x,y) as fixed
  768.         // so we don't trigger again and so we don't drop it believing
  769.         // that it's redundant. It would be nice to handle this in
  770.         // the post-sequence, but, unfortunately, we need to get the
  771.         // order straightened out before further moves and inserts happen.
  772.  
  773.         var c = arg == "local" ? sc : lc;
  774.         var set = arg == "local" ? localCS.set : serverCS.set;
  775.         var i = arg == "local" ? l : s;
  776.         c.fixed = true;
  777.  
  778.         // Before we duplicate the command, we must ensure
  779.         // that x (as above) still exists on the side which is to
  780.         // receive the duplicate command.  If it's been deleted, 
  781.         // we can drop the R(x,y), as x's position is irrelevant.
  782.         // See #7379.
  783.         var nodeset = arg == "local" ? local : server;
  784.         if (nodeset.Node(c.nid, false, true) ==  null) {
  785.             return do_drop(arg == "local" ? "server" : "local");
  786.         }
  787.  
  788.         Xmarks.LogWrite("Duplicating command from " + arg + ": " + c.toSource());
  789.  
  790.         // This bit is tricky. Insert our copy of the command c in
  791.         // the appropriate place in set. The appropriate place is the first
  792.         // non-fixed spot after the current command.
  793.  
  794.         for ( i++; i < set.length; ++i) {
  795.             if (!set[i].fixed)
  796.                 break;
  797.         }
  798.  
  799.         set.splice(i, 0, c);
  800.         l = -1;
  801.         breakOut = true;
  802.         return;
  803.     }
  804. }
  805.  
  806.  
  807. function NearestAncestor(nid, baseline, ns1, ns2) {
  808.     while (nid) {
  809.         var node = baseline.Node(nid, false, true);
  810.         if (!node) {
  811.             throw Error("NearestAncestor failed accessing " + nid);
  812.         }
  813.  
  814.         if (ns1.Node(nid, false, true) && ns2.Node(nid, false, true)) {
  815.             return nid;
  816.         }
  817.  
  818.         nid = node.pnid;
  819.     }
  820.     throw "Couldn't find a common ancestor!";
  821. }
  822.  
  823. function ResurrectNodes(nid, baseline, source, target, sourceCS, sourceIndex, 
  824.     del, delCS, delIndex, bnid) {
  825.     var nids = [nid];
  826.     var pnid = null;
  827.  
  828.     while (nids.length) {
  829.         var nid = nids.shift();
  830.         var node = baseline.Node(nid);
  831.         var sourceNode = source.Node(nid, false, true);
  832.         var delpos = del.deleted.indexOf(nid);
  833.  
  834.         // Process this nid only if:
  835.         // * If was deleted by the given delete commandi and
  836.         // * It still exists in the source and
  837.         // * Its has the same parent in baseline and source
  838.         //   or it's the root of what we're resurrecting.
  839.         if (delpos >= 0 && sourceNode && 
  840.                 (!pnid || sourceNode.pnid == node.pnid)) {
  841.             var args = sourceNode.GetSafeAttrs();
  842.             if (!pnid) {
  843.                 // This is our root; override the pnid and bnid if given.
  844.                 pnid = NearestAncestor(args.pnid, baseline, source, target);
  845.                 args.pnid = pnid;
  846.                 if (bnid) {
  847.                     args.bnid = bnid;
  848.                 }
  849.             }
  850.             sourceCS.set.splice(sourceIndex++, 0,
  851.                 new Command("insert", nid, args));
  852.  
  853.             // If this nid was to be modified, drop the command as
  854.             // it is now redundant (we're going to insert the full
  855.             // node in its final state with the new command added above).
  856.             forEach(sourceCS.set, function(cmd, index) {
  857.                 if (cmd.action == 'update' && cmd.nid == nid) {
  858.                     sourceCS.drop(index);
  859.                 }
  860.             });
  861.  
  862.             // Remove this nid from the list of nids deleted by the delete
  863.             // command. This prevents triggering conflicts between the
  864.             // delete command and the insert we just added above.
  865.             if (delpos >= 0) {
  866.                 del.deleted.splice(delpos, 1);
  867.             }
  868.             if (node.children) {
  869.                 forEach(node.children, function(nid) { nids.push(nid) } );
  870.             }
  871.         }
  872.     }
  873.     // Finally, if our delete command now no longer deletes anything,
  874.     // delete it!
  875.     if (!del.deleted.length) {
  876.         delCS.drop(delIndex);
  877.     }
  878.  
  879.     return pnid;
  880. }
  881.